From : www.LeetCode.com
Description
Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
中文介绍
描述
给定一个数组和一个值，要求返回一个新的数组长度，在这个新的数组长度范围内，没有给定的这个值。还不能使用额外的空间，只能在原数组中操作。
也就是说，给定一个数组，和一个数。要求将这个数全部移到这个数组的最后面，并返回一个新的数组长度（从0索引到最后一个不是该数的元素）。
例子
例如给一个数组nums = [3,2,2,3]，一个数 val = 3。
将数组中所有的3移动到数组的最后面。
移动后的数组为 nums = [2,2,3,3]。
从第一个元素到最后一个不是val的元素的长度为2（也就是前两个元素）。
因此，程序的返回值应当为2。
解决方案一
本方案的思想：
先统计出有多少个val元素，假如有count个val元素,
那么将数组分为0到nums.length-count-1和nums.length-count到nums.length两部分。
后面count个元素用来存放val，前面nums.length-count-1个元素就是想要的结果了。
总的来说就是把非val元素全部放在前面，val元素全部放在后面。
代码实现（JAVA）
class Solution {
public int removeElement(int[] nums, int val) {
int count = 0;
//统计出val的个数
for(int i = 0; i<nums.length; i++){
if(nums[i] == val){
count++;
}
}
//保证前nums.length-count个元素中，没有val元素
for(int k = 0; k<nums.length-count; k++){
if(nums[k] == val){
for(int j = nums.length-count; j<nums.length; j++){
if(nums[j] != val){
int temp = 0;
temp = nums[j];
nums[j] = nums[k];
nums[k] = temp;
break;
}
}
}
}
return nums.length-count;
}
}
解决方案二
本方案的思想：
定义一个指针index，初始时指向数组的第一个元素。
遍历数组，如果遇到非val的元素，就把当前元素与index指向的元素交换位置，并把index指针后移一位。
相当于把所有的非val元素从第一号元素一直往后排，最终达到将所有val元素放在数组的后面的目的。
虽然会有一些无用交换，但是效率相比方案一提高了很多。
代码实现
class Solution {
public int removeElement(int[] nums, int val) {
int index = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] != val) {
nums[index] = nums[j];
index++;
}
}
return index;
}
}
总结
解决同样的问题，方案二显然效率提高很多。解决问题时应该多方面思考，最好要排除想到的第一个解决方案，再思考有没有其他的解法。往往想到的第一个解决方案并不够优秀。。。
（注：方案一是我自己写的，方案二是其他人提交的解决方案，提交完之后浏览别人的解决方案，才发现自己的算法是多么低效。。。）
